package top.humbleyuan.leet.datastructure.unionfind;

/**
 * @Author HumbleYuan
 * @Date 2020/5/11 19:36
 * @Des 并查集
 */
public class UnionFind {

    private int[] array;

    UnionFind(int n){
        array=new int[n];
        for(int i = 0; i<array.length; i++) {
            array[i] = -1;//初始化为-1；
        }
    }

    public int find(int x) {
        while(array[x] != -1) {
            x = array[x];
        }
        return x;
    }

    public void union(int a,int b) {
        int roota = find(a);
        int rootb = find(b);
        if(roota !=  rootb)
            array[roota] = rootb;//若两个节点不是同一个根，则连接起来。
    }

    // 两个元素是否在同一个集合
    public boolean connected(int a,int b) {
        int roota = find(a);
        int rootb = find(b);
        if(roota == rootb)
            return true;
        return false;
    }

    public int count() {
        int count=0;//能够形成几棵独立的树（集合）。
        for(int i=0;i < array.length; i++) {
            if(array[i]==-1)
                count++;
        }
        return count;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        UnionFind ufs = new UnionFind(10);

        ufs.union(4,3);
        ufs.union(3,8);
        ufs.union(6,5);
        ufs.union(9,4);
        ufs.union(2,1);

        System.out.println(ufs.count());
        System.out.println(ufs.connected(0, 7));
        System.out.println(ufs.connected(8, 9));
    }

}
